#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 205;
array <int, N * N> g, fac, f[N];
int pow_(int x, int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = ans * x % p;
		x = x * x % p;
		k >>= 1;
	}
	return ans;
}
signed main() {
	freopen("pr.in", "r", stdin);
	freopen("pr.out", "w", stdout);
	int p = read();
	int T = read();
	fac[0] = 1;
	for (int i = 1; i <= 2000; i++)
		fac[i] = fac[i - 1] * i % p;
	while (T--) {
		int n = read(), m = read();
		for (int i = 1; i <= 200; i++)
			f[i].fill(0);
		g.fill(0);
		f[0][0] = 1, g[0] = 1;
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= n * m; j++) {
				for (int k = 0; k <= m && k <= j; k++) {
					f[i][j] += f[i - 1][j - k];
					if (f[i][j] >= p) f[i][j] -= p;
				}
			}
		}
		int M = 0;
		for (int i = 0; i <= n * m; i++) {
			if (i) M += f[n][i - 1];
			if (M >= p) M -= p;
			ans += M * f[n][i] % p;
			if (ans >= p) ans -= p;
		}
		write(pow_(ans, p - 2, p)), puts("");
	}

	return 0;
}
